package jianzhiOffer;

public class num13 {
    public int movingCount(int m, int n, int k) {
        if(k == 0) {
            return 1;
        }
        boolean[][] arr = new boolean[m][n];
        arr[0][0] = true;
        int ans = 1;
        for(int i = 0;i < m;i ++) {
            for(int j = 0;j < n;j ++) {
                if((i == 0 && j == 0) ||get(i) + get(j) > k) continue;
                if(i - 1 >= 0) {
                    arr[i][j] |= arr[i - 1][j];
                }
                if(j - 1 >= 0) {
                    arr[i][j] |= arr[i][j - 1];
                }
                ans += arr[i][j] ? 1 : 0;
            }
        }
        return ans;
    }
    public int get(int i) {
        int sum = 0;
        while(i > 0) {
            sum += i % 10;
            i = i / 10;
        }
        return sum;
    }
}
